package others;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class Test84again {
    /**
     * 84. 柱状图中最大的矩形
     * 给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
     * <p>
     * 求在该柱状图中，能够勾勒出来的矩形的最大面积。
     * 输入：heights = [2,1,5,6,2,3]
     * 输出：10
     * 解释：最大的矩形为图中红色区域，面积为 10
     */

    public static int largestRectangleArea(int[] heights) {

        int len = heights.length;
        int res = 0;
        Set staffsSet = new HashSet<>();
        for (int i = 0; i < heights.length; i++) {
            staffsSet.add(heights[i]);
        }


        if (staffsSet.size() == 1) {
            res = heights[0] * heights.length;
            return res;
        }

        for (int j = len; j > 0; j--) {
            int k = 0;
            while (k <= len - j) {
                int[] ints = Arrays.copyOfRange(heights, k, j + k);
                int min = min(ints);
                res = min * j > res ? min * j : res;
                k++;
            }
        }
//            for(int i=0; i<= len-j; i++){
//                int[] ints = Arrays.copyOfRange(heights, i, j+i);
//                int min = min(ints);
//                res = min * j > res ? min * j : res;
//                System.out.println(ints);
//            }
        return res;
    }

    static int min(int[] arr) {
        int min = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (min > arr[i]) {
                min = arr[i];
            }
        }
        return min;
    }

    public static void main(String[] args) {
        int arr[] = {2,1,5,6,2,3};

        System.out.println(largestRectangleArea(arr));
    }
}
